package com.zhugang.week03;

import java.util.Stack;

/**
 * @program algorithms
 * @description: dailyTemperatures: 单调栈.739每日温度
 * @author: chanzhugang
 * @create: 2022/06/03 23:58
 */
public class DailyTemperatures {

    public static void main(String[] args) {
        int[] arr = new int[]{73, 74, 75, 71, 69, 72, 76, 73};
        DailyTemperatures dailyTemperatures = new DailyTemperatures();
        // int[] result = dailyTemperatures.dailyTemperatures1(arr);
        int[] result = dailyTemperatures.dailyTemperatures2(arr);

        for (int i : result) {
            System.out.println(i);
        }
    }

    /**
     * 暴力求解：O(n^2)
     * s
     *
     * @param arr
     * @return
     */
    public int[] dailyTemperatures1(int[] arr) {
        // 两重for，内层元素和外层元素比较，满足条件，计算下标差，跳出内层循环
        int n = arr.length;
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (arr[j] > arr[i]) {
                    result[i] = j - i;
                    break;
                }
            }
        }
        return result;
    }

    /**
     * 单调栈:O(n)
     *
     * @param arr
     * @return
     */
    public int[] dailyTemperatures2(int[] arr) {
        // 此种解法比较难想，比暴力解法时间复杂度低，不好分析
        // 单调栈：遍历数组；遍历栈，如果arr[栈顶元素]< 数组元素，计算下标差值，栈顶元素弹出；元素下标压入栈
        int n = arr.length;
        int[] result = new int[n];
        // stack存储元素下标
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            while (!stack.empty() && arr[stack.peek()] < arr[i]) {
                Integer idx = stack.pop();
                // 注意这个下标
                result[idx] = i - idx;
            }
            stack.push(i);
        }
        return result;
    }

}